#include "linklist.h"

/*
头指针是头节点的指针
当链表为空时，头节点指向空地址NULL
当链表不为空时，头节点指向表头节点
*/

/*******************************************************************************
*函数名：
*函数功能：创建空链表
*函数参数：
*函数返回值：pnode,创建的链表的头指针
*函数说明：
*******************************************************************************/
pnode creat_linklist(void)
{
	pnode p = (pnode)malloc(sizeof(NODE));
	if(p == NULL)
	{
		perror("malloc");
		exit(1);
	}
	p->next = NULL;
	
	return p;
}

/*******************************************************************************
*函数名：
*函数功能：插入一个节点
*函数参数：	pnode pre,插入位置的前一节点的指针
					pnode pins,插入节点的指针
*函数返回值：
*函数说明：
*******************************************************************************/
void insert_node(pnode pre,pnode pins)
{
	pins->next = pre->next;
	pre->next = pins;
}


/*******************************************************************************
*函数名：
*函数功能：删除一个节点
*函数参数：pnode pre,要删除的节点的前一节点的指针
*函数返回值：
*函数说明：
*******************************************************************************/
void delete_node(pnode pre)
{
	/*判断要删除的节点是否存在*/
	if (isempty_linklist(pre))
	{
		printf("该节点不存在，无法删除。\n");
		return;
	}
	
	/*删除节点*/
	pnode temp = pre->next;
	pre->next = temp->next;
	free(temp);
}

/*******************************************************************************
*函数名：
*函数功能：判断链表是否为空
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
bool isempty_linklist(pnode head)
{
	if (head->next == NULL)
		return true;
	else
		return false;
}

/*******************************************************************************
*函数名：
*函数功能：打印链表
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void print_linklist(pnode head)
{
	pnode p = head;
	printf("--------------------------------------------\n");
	printf("head");
	for(p = head->next;p != NULL;p = p->next)
	{
		printf("->%d",p->data);
	}
	printf("->NULL\n");
	printf("--------------------------------------------\n");
}

/*******************************************************************************
*函数名：
*函数功能：逆转链表
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void reverse_linklist(pnode head)
{
	pnode p,q;
	p = head->next;
	head->next = NULL;

	while(p != NULL)
	{
		q = p;
		p = p->next;
		insert_node(head,q);		
	}
}


/*******************************************************************************
*函数名：
*函数功能：删除指定数据对应的节点
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void delete(pnode head,int data)
{
	pnode p = head;
	while(p->next->data != data)
	{
		p = p->next;
		if (p == NULL)
		{
			printf("该数据对应节点不存在，无法删除。\n");
			return;
		}
	}
	
	delete_node(p);
}

/*******************************************************************************
*函数名：
*函数功能：剪切一个节点（从链表中断开，但不释放）
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/
void cut_node(pnode ppre)
{
	/*判断链表是否为空*/
	if (isempty_linklist(ppre))
	{
		printf("链表只有一个节点，无法剪切\n");
		return;
	}
	
	/*剪切节点*/
	ppre->next = ppre->next->next;
}


/*******************************************************************************
*函数名：
*函数功能：特殊奇偶排序
*函数参数：
*函数返回值：
*函数说明：奇数节点正序，偶数节点逆序，且奇数节点在偶数节点前面。
例如，1 2 3 4 5 6 7 8 9→1 3 5 7 9 8 6 4 2
*******************************************************************************/
void sort_oddeven(pnode head)
{
	pnode p,q,r;
	p = head;
	q = head;
	r = head;
	while(p->next != NULL)
		p = p->next;//始终保持指针p指向初始表的表尾
	
	while(q->next != p)
	{
		q = q->next;
		
		if ((q->next->data)%2 == 0)//如果q的下一个节点的数据是偶数
		{
			r = q->next;
			cut_node(q);//剪切q的下一个节点
			insert_node(p,r);
		}
	}
}

/*******************************************************************************
*函数名：
*函数功能：
*函数参数：
*函数返回值：
*函数说明：
*******************************************************************************/



